package q558_intersect;


class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    public Node() {}

    public Node(boolean _val,boolean _isLeaf,Node _topLeft,Node _topRight,Node _bottomLeft,Node _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
}

public class Solution {
    /*
    核心在于判断
    如果一个树的isLeaf是1 当它的val也是1的时候 可以直接返回 它自己 当它的val不是1的时候 可以直接返回 另一个
    只有当两个数的isLeaf都是0的情况才需要 递归运算
     */
    public Node intersect(Node quadTree1, Node quadTree2) {
        if (quadTree1 == null) return null;
        if (quadTree1.isLeaf) {
            if (quadTree1.val) return quadTree1;
            return quadTree2;
        }
        if (quadTree2.isLeaf) {
            if (quadTree2.val) return quadTree2;
            return quadTree1;
        }
        Node tl = intersect(quadTree1.topLeft, quadTree2.topLeft);
        Node tr = intersect(quadTree1.topRight, quadTree2.topRight);
        Node bl = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
        Node br = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
        if (tl.isLeaf && tr.isLeaf && bl.isLeaf && br.isLeaf && tl.val == tr.val && tr.val == bl.val && bl.val == br.val){
            return new Node(tl.val,true,null,null,null,null);
        }else{
            return new Node(quadTree1.val|quadTree2.val,false,tl,tr,bl,br);
        }
    }
}
